\documentclass[UTF8]{ctexart}
\usepackage{amsmath}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{mathrsfs}
\usepackage{mathrsfs}
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{epstopdf}
\usepackage{indentfirst}
\usepackage{caption}
\usepackage{float}
\usepackage{geometry}
\setlength{\parskip}{0.5em}
\geometry{a4paper,scale=0.73}
\pagenumbering{arabic}
% info
\title{AI 第二次作业}
\author{刘本宸 22920202200764}
\date{\today}
\begin{document}
\maketitle
\tableofcontents
\makeatletter %使\section中的内容左对齐
\renewcommand{\section}{\@startsection{section}{1}{0mm}
    {-\baselineskip}{0.5\baselineskip}{\bf\leftline}}
\makeatother
\newpage

\section{Q1}
\paragraph{模型 Machine-Learning Ben-Chen(MLBC)}
代码文件保存在同级别的program目录之下，可以直接打开查看。
\paragraph{}
README.md 中已经写明了模型的使用方法，也生成了对应的数据集，可以直接在demo.py中调用对应函数。

\paragraph{}
% \newpage
\section{Q2}
\subsection{(1)}
\paragraph{}已知对于数据$ X_n \in R^{n \times d} $, 标签$Y_n \in R^{n \times 1} $所组成的线性模型，我们有以下线性参数解.

\begin{equation}
    W_n = (X_n^TX_n)^{-1}X_n^TY_n
\end{equation}
\paragraph{}在加入一行数据 $x \in R^{1 \times d}$，使得 $X_{n+1} = \left( \begin{array}{l}X_n\\x\end{array}\right)$。下面先求$W_{n+1}$的表达式。
\begin{equation}
    W_{n+1}= (X_{n+1}^TX_{+1}n)^{-1}X_{n+1}^TY_{n+1}
\end{equation}
\paragraph{}接下来根据分块矩阵的性质和Sherman-Morrison-Woodbury公式，有如下$(X_{n+1}^TX_{n+1})^{-1}$与$(X_n^TX_n)^{-1}$的关系。
\begin{equation}
    (X_{n+1}^TX_{n+1}) = \begin{pmatrix}  X_n^T & x^T  \end{pmatrix} \begin{pmatrix}  X_n \\ x  \end{pmatrix}
\end{equation}
\begin{equation}
    (X_{n+1}^TX_{n+1})^{-1} = (X_n^TX_n)^{-1} - (X_n^TX_n)^{-1}x^T(1+x(X_n^TX_n)^{-1}x^T)^{-1}x(X_n^TX_n)^{-1}
\end{equation}
\paragraph{}接下来根据分块矩阵的性质，有：
\begin{equation}
    (X_{n+1}^TY_{n+1}) = \begin{pmatrix}  X_n^T & x^T  \end{pmatrix} \begin{pmatrix}  Y_n \\ y  \end{pmatrix} = X_n^TY_n+x^Ty
\end{equation}
\paragraph{}将(4),(5)带入到(2)中我们可以得到：
\begin{center}
    \begin{equation}
        \begin{split}
            W_{n+1} = W_n+ \alpha x^T(xW_n-y)
            \\
            \alpha = (1+x(X_n^TX_n)^{-1}x^T)^{-1}(X_n^TX_n)^{-1}
        \end{split}
    \end{equation}
\end{center}

\newpage
\subsection{(2)}
\paragraph{}
对于原数据 $X_d \in R^{n \times d}$，我们增加一个特征维度，使得数据变为$X_{d+1} \in R^{n \times (d+1)}$。
根据已知我们可以得到如下两个式子。
\begin{equation}
    \begin{cases}
        W_d = (X_d^TX_d)^{-1}X_d^TY_n
        \\
        W_{d+1} = (X_{d+1}^TX_{d+1})^{-1}X_{d+1}^TY_n
    \end{cases}
\end{equation}
\paragraph{}通过使用分块矩阵的性质我们有：
\begin{equation}
    W_{d+1} = \begin{pmatrix}
        X_d^TX_d & X_d^TXx \\
        x^TX_n   & x^Tx
    \end{pmatrix}^{-1}
    \begin{pmatrix}
        X_d^T \\ x^T
    \end{pmatrix}
    Y_n
\end{equation}
\paragraph{}根据矩阵求逆的性质我们有：
\begin{equation}
    W_{d+1} =
    \begin{pmatrix}
        A & B \\
        C & D
    \end{pmatrix}_{(d+1) \times (d+1)}
    \begin{pmatrix}
        X_d^TY_n \\
        x^TY_n
    \end{pmatrix}_{(d+1) \times 1}
    =
    \begin{pmatrix}
        AX_d^TY_n+Bx^TY_n \\
        CX_d^TY_n+Dx^TY_n
    \end{pmatrix}
\end{equation}
\paragraph{}其中，A，B，C，D分别为：
\begin{flushleft}
    \begin{equation}
        \begin{cases}
            A_{d \times d} = (X_d^TX_d)^{-1}+X_d^TX_d)^{-1}X_d^Tx(x^Tx-x^TX_d(X_d^TX_d)^{-1}X_d^Tx)^{-1}x^TX_d(X_d^TX_d)^{-1}
            \\
            B_{d \times 1} = -(X_d^TX_d)^{-1}X_d^Tx(x^Tx-x^TX_d(X_d^TX_d)^{-1}X_d^Tx)^{-1}
            \\
            C_{1 \times d} = -(x^Tx-x^TX_d(X_d^TX_d)^{-1}X_d^Tx)^{-1}x^TX_d(X_d^TX_d)^{-1}
            \\
            D_{1 \times 1} = (x^Tx-x^TX_d(X_d^TX_d)^{-1}X_d^Tx)^{-1}
        \end{cases}
    \end{equation}
\end{flushleft}
\paragraph{}带入到我们上面的公式(8)，最后可以整理成如下形式：
\begin{equation}
    \begin{cases}
        W_{d+1} =
        \begin{pmatrix}
            W_d + \beta (X_d^TX_d)^{-1}X_d^Txx^TX_dW_d - \beta(X_d^TX_d)^{-1}X_d^Tx x^TY_n
            \\
            \beta (x^TY_n - x^TX_dW_d)
        \end{pmatrix}
        \\
        \beta = (x^Tx-x^TX_d(X_d^TX_d)^{-1}X_d^Tx)^{-1}
    \end{cases}
\end{equation}
\paragraph{}得证。

\newpage
\subsection{(3)} 已知$X_d \in R^{(n \times d)}$, $Y_d  \in R^{(n \times 1)}$,$x \in R^{1 \times d}$,$x_{d+1} \in R^{(n+1) \times 1}$.
\paragraph{}则我们有： $X_{n+1} = \left( \begin{array}{l}X_d\\x\end{array}\right)$,  $X_{n+1,d+1} = \begin{pmatrix}X_{n+1} & x_{d+1}\end{pmatrix}$, $Y_{n+1} = \left( \begin{array}{l}Y_n\\y\end{array}\right)$。

\paragraph{}先使用第一问的公式将$W_{n , d}$化简为$W_{(n+1) , d}$
\begin{equation}
    \begin{split}
        W_{(n+1) , d} = W_{n , d}+ \alpha x^T(xW_{n , d}-y)
        \\
        \alpha = (1+x(X_d^TX_d)^{-1}x^T)^{-1}(X_d^TX_d)^{-1}
    \end{split}
\end{equation}
\paragraph{}再使用第二问的公式将$W_{(n+1) , d}$化简为$W_{(n+1) , (d+1)}$
\begin{equation}
    \begin{cases}
        W_{d+1 , n+1} =
        \begin{pmatrix}
            W_{(n+1),d} + \beta (X_{n+1}^TX_{n+1})^{-1}X_{n+1}^Tx_{d+1}x_{d+1}^TX_dW_{(n+1),d} - \beta(X_d^TX_d)^{-1}X_d^Tx_{d+1} x_{d+1}^TY_{n+1}
            \\
            \beta (x_{d+1}^TY_n - x_{d+1}^TX_{n+1}W_{(n+1),d})
        \end{pmatrix}
        \\
        \beta = (x_{d+1}^Tx_{d+1}-x_{d+1}^TX_d(X_d^TX_d)^{-1}X_d^Tx_{d+1})^{-1}
    \end{cases}
\end{equation}
\paragraph{}则可以得到最终结果：
\begin{equation}
    \begin{cases}
        W_{(n+1) , d} = W_{n , d}+ \alpha x^T(xW_{n , d}-y)
        \\
        \alpha = (1+x(X_d^TX_d)^{-1}x^T)^{-1}(X_d^TX_d)^{-1}
        \\
        W_{d+1 , n+1} =
        \begin{pmatrix}
            W_{(n+1),d} + \beta (X_{n+1}^TX_{n+1})^{-1}X_{n+1}^Tx_{d+1}x_{d+1}^TX_dW_{(n+1),d} - \beta(X_d^TX_d)^{-1}X_d^Tx_{d+1} x_{d+1}^TY_{n+1}
            \\
            \beta (x_{d+1}^TY_n - x_{d+1}^TX_{n+1}W_{(n+1),d})
        \end{pmatrix}
        \\
        \beta = (x_{d+1}^Tx_{d+1}-x_{d+1}^TX_d(X_d^TX_d)^{-1}X_d^Tx_{d+1})^{-1}
    \end{cases}
\end{equation}
\end{document}